/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
class Solution
{
private:
    vector<string> res;
    vector<string> path;
    bool isOk( string &s)
    {
        //判断字符串是否合法
        if (s.size() > 1 && s[0] == '0')
        {
            return false;
        }
        for (int i = 0; i < s.size(); i++)
        {
            //判断字符是否合法
            if (s[i] - '0' < 0 || s[i] - '0' > 9)
            {
                return false;
            }
        }
        //现在全是数字
        int tmp = atoi(s); //转换成数字
        if (tmp < 0 || tmp > 255)
        {
            return false;
        }
        return true;
    }
    void backtracking(const string &s, int pointnum, int index)
    {
        //因为分四段 其实第四段不用再分
        if (pointnum == 3)
        {
            string str = s.substr(index, s.size() - index);
            if (isOk(str))
            {
                path.push_back(str);
                string ss = "";
                for (int i = 0; i < 4; i++)
                {
                    ss += path[i];
                }
                res.push_back(ss);
                return;
            }
        }
        for (int i = index; i < s.size(); i++)
        {
            string str = s.substr(index, i - index);
            if (isOk(str))
            {
                path.push_back(str);
            }
            else
            {
                continue;
            }
            backtracking(s, pointnum + 1, i + 1);
            path.pop_back();
        }
    }

public:
    vector<string> restoreIpAddresses(string s)
    {
        //实际就是分成四段 也是回溯的思路
        backtracking(s, 0, 0);
        return res;
    }
};
// @lc code=end
